package ans.p40;

import test.Entrance;

import java.util.*;

/**
 * #      40
 * 名称   组合总和 II
 * 链接   https://leetcode-cn.com/problems/combination-sum-ii
 * 题解   [964](https://leetcode-cn.com/problems/combination-sum-ii/solution)
 * 通过率 63.8%
 * 难道   中等
 */

public class Solution {
    @Entrance
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        Arrays.sort(candidates);
        Set<String> set = new HashSet<>();
        traceback(set, ans, candidates, list, target, 0);
        return ans;
    }

    private void traceback(Set<String> set, List<List<Integer>> ans, int[] candidates, List<Integer> list, int target, int index) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            ArrayList<Integer> integers = new ArrayList<>(list);
            if (set.add(integers.toString())) {
                ans.add(integers);
            }
        }
        for (int i = index; i < candidates.length; i++) {
            list.add(candidates[i]);
            traceback(set,ans, candidates, list, target - candidates[i], i + 1);
            list.remove(list.size() - 1);
        }


    }
}